package com.cty.twentyNinethDay;

import java.util.HashMap;

/*
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
*/
public class Q_48 {
    // 力扣官方题解 方法一:深度优先搜索
    /*
     * 思路:
     *   将所有的路线全部找出
     *   判断是否等同于targetSum
     *   时间复杂度O(n * 2) 空间复杂度O(n)
     * */
    public int pathSum(TreeNode root, long targetSum) {
        if (root == null) return 0;
        int res = rootSum(root, targetSum);
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
    }

    // 计算出当前节点有个路径符合
    public int rootSum(TreeNode root, long target) {
        int ret = 0;
        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == target) {
            ret++;
        }
        ret += rootSum(root.left, target - val);
        ret += rootSum(root.right, target - val);
        return ret;
    }

    // 力扣官方题解 方法二:前缀和
    /*
     * 思路:
     *   我们用一个哈希表来记录本次路径的前缀和
     *   然后判断当前的前缀和 - taegetNum是否
     *   存在，存在就加入存在次数 不存在就加入
     *   哈希表中 递归左右子节点继续判断
     *   时间复杂度O(n) 空间复杂度O(n)
     * */
    public int rootSum2(TreeNode root, long targetSum) {
        HashMap<Long, Integer> map = new HashMap<>();
        map.put(0L,1);
        return dfs(root, targetSum, map, 0);
    }

    public int dfs(TreeNode root, long target, HashMap<Long, Integer> map, long cur) {
        if (root == null) return 0;
        int ret = 0;
        cur += root.val;
        ret = map.getOrDefault(cur - target, 0);
        map.put(cur, map.getOrDefault(cur, 0) + 1);
        ret += dfs(root.left, target, map, cur);
        ret += dfs(root.right, target, map, cur);
        map.put(cur, map.getOrDefault(cur, 0) - 1);
        return ret;
    }
}
